public class Test {

    //合并两个有序链表
    public static MySingleList.ListNode combine
            (MySingleList.ListNode head1, MySingleList.ListNode head2)
    {
        MySingleList.ListNode newHead = new MySingleList.ListNode(0);
        MySingleList.ListNode tmp = newHead;
        while(head1 != null && head2 != null){
            if(head1.val <= head2.val){
                tmp.next = head1;
                head1 = head1.next;
            }else{
                tmp.next = head2;
                head2 = head2.next;
            }
            tmp = tmp.next;
        }
        if(head1 != null){
            tmp.next = head1;
        }
        if(head2 != null){
            tmp.next = head2;
        }
        return tmp.next;
    }

    //寻找第一个相同的节点
    public static MySingleList.ListNode getInterSectionNode
    (MySingleList.ListNode headA, MySingleList.ListNode headB) {
        if(headA == null && headB == null){
            return null;
        }
        //分别求两个链表的长度
        int lenA = 0;
        int lenB = 0;
        MySingleList.ListNode pl = headA;
        MySingleList.ListNode ps = headB;
        while(pl != null){
            lenA++;
            pl = pl.next;
        }
        while(ps != null){
            lenB++;
            ps = ps.next;
        }
        //要指回来
        pl = headA;
        ps = headB;
        int len = lenA - lenB;
        //根据length的值，修改指向
        if(len < 0){
            pl = headB;
            ps = headA;
            len = lenB - lenA;
        }
        //len一定是正数，pl指向的一定是较长的
        while(len != 0){
            pl = pl.next;
            len--;
        }
        while(pl != ps){
            pl = pl.next;
            ps = ps.next;
        }
        return pl;
    }
    //两个链表建立相交
    public static void createCut
    (MySingleList.ListNode headA, MySingleList.ListNode headB){
        headA.next = headB;
    }

    public static void main(String[] args) {
        MySingleList mySingleList1 = new MySingleList();
        mySingleList1.createList(12,45);
        mySingleList1.addFirst(15);
        mySingleList1.addLast(13);
//        mySingleList1.display();
//        System.out.println("==========");
//        mySingleList1.display();
//        System.out.println(mySingleList1.contains(12));
//        System.out.println("==========");
//        mySingleList1.getSize();

//        System.out.println("=====增加头结点=====");
//        mySingleList1.addFirst(80);
//        mySingleList1.display();

//        System.out.println("=====增加尾节点=====");
//        mySingleList1.addLast(19);
//        mySingleList1.display();

//        System.out.println("=====任意位置插入=====");
//        mySingleList1.addIndex(93,0);
//        mySingleList1.addIndex(23,0);
//        mySingleList1.addIndex(39,4);
//        mySingleList1.display();

//        System.out.println("=====删除单个key节点=====");
//        mySingleList1.remove(93);
//        mySingleList1.display();

//        System.out.println("=====删除所有key节点=====");
//        mySingleList1.removeAllKey(23);
//        mySingleList1.display();

//        System.out.println("=====清空链表=====");
//        mySingleList.clear();
//        mySingleList.display();

//        System.out.println("=====反转链表=====");
//        MySingleList.ListNode ret = mySingleList1.reverseList();
//        mySingleList1.display(ret);

//        System.out.println("=====寻找中间节点======");
//        MySingleList.ListNode mid = mySingleList1.findMiddle();
//        System.out.println(mid.val);

//        System.out.println("=====寻找倒数第k个节点=====");
//        MySingleList.ListNode k = mySingleList1.findK(5);
//        System.out.println(k.val);

//        System.out.println("==================");
        //创建第二个链表
//        MySingleList mySingleList2 = new MySingleList();
//        mySingleList2.createList(12,50);
//        mySingleList2.addFirst(5);
//        mySingleList2.addFirst(4);
//        mySingleList2.addFirst(1);
//        mySingleList2.display();

//        System.out.println("=====合并两个链表=====");
//        combine(mySingleList1.head,mySingleList2.head);
//        mySingleList2.display();

//        System.out.println("=====判断回文=====");
//        MySingleList mySingleList3 = new MySingleList();
//        mySingleList3.createList(11,22);
//        mySingleList3.addLast(33);
//        mySingleList3.addLast(22);
//        mySingleList3.addLast(11);
//        mySingleList3.display();
//        boolean b = mySingleList3.chkPalindrome();
//        System.out.println(b);

//        System.out.println("========寻找第一个相同的节点==========");
//        createCut(mySingleList2.head , mySingleList1.head);
//        MySingleList.ListNode d = getInterSectionNode(mySingleList1.head , mySingleList2.head );
//        System.out.println(d.val);

//        System.out.println("=====判断环=====");
//        mySingleList1.createLoop();
//        boolean b = mySingleList1.hasCycle();
//        System.out.println(b);

    }
}

